home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / mawk10.zip / REXP3.C < prev    next >
C/C++ Source or Header  |  1991-10-05  |  8KB  |  284 lines
  1.  
  2. /********************************************
  3. rexp3.c
  4. copyright 1991, Michael D. Brennan
  5.  
  6. This is a source file for mawk, an implementation of
  7. the AWK programming language.
  8.  
  9. Mawk is distributed without warranty under the terms of
  10. the GNU General Public License, version 2, 1991.
  11. ********************************************/
  12.  
  13. /*$Log:    rexp3.c,v $
  14.  * Revision 3.3  91/08/13  09:10:18  brennan
  15.  * VERSION .9994
  16.  * 
  17.  * Revision 3.2  91/06/10  16:18:17  brennan
  18.  * changes for V7
  19.  * 
  20.  * Revision 3.1  91/06/07  10:33:28  brennan
  21.  * VERSION 0.995
  22.  * 
  23.  * Revision 1.4  91/05/31  10:56:32  brennan
  24.  * stack_empty hack for DOS large model
  25.  * 
  26. */
  27.  
  28. /*  match a string against a machine   */
  29.  
  30. #include "rexp.h"
  31.  
  32.  
  33. /*  check that a bit is on  */
  34. #define  ison(b,x) ( (b)[(x)>>3] & ( 1 << ((x)&7)  ))
  35.  
  36.  
  37. extern RT_STATE *RE_run_stack_base; 
  38. extern RT_STATE *RE_run_stack_limit ;
  39. extern RT_STATE *RE_run_stack_empty ;
  40.  
  41. RT_STATE  *RE_new_run_stack() ;
  42.  
  43.  
  44. #define  push(mx,sx,ssx,ux)   if (++stackp == RE_run_stack_limit)\
  45.                                 stackp = RE_new_run_stack() ;\
  46.                stackp->m=mx;stackp->s=sx;stackp->ss=ssx;stackp->u=ux;
  47.  
  48.  
  49. #define   CASE_UANY(x)  case  x + U_OFF :  case  x + U_ON
  50.  
  51. /* returns start of first longest match and the length by
  52.    reference.  If no match returns NULL and length zero */
  53.  
  54. char *REmatch(str, machine, lenp)
  55.   char *str ;
  56.   VOID   *machine ;
  57.   unsigned *lenp ;
  58. { register STATE *m = (STATE *) machine ;
  59.   register char *s = str ;
  60.   char *ss ;
  61.   register RT_STATE *stackp ;
  62.   int u_flag ;
  63.   char *str_end, *ts ;
  64.  
  65.   /* state of current best match stored here */
  66.   char *cb_ss ;  /* the start */
  67.   char *cb_e  ;  /* the end , pts at first char not matched */
  68.  
  69.   *lenp = 0 ;
  70.  
  71.   /* check for the easy case */
  72.   if ( (m+1)->type == M_ACCEPT && m->type == M_STR )
  73.   { if ( ts = str_str(s, m->data.str, m->len) ) *lenp = m->len ;
  74.     return ts ;
  75.   }
  76.     
  77.   u_flag = U_ON ; cb_ss = ss = str_end = (char *) 0 ;
  78.   stackp = RE_run_stack_empty ;
  79.   goto  reswitch ;
  80.  
  81. refill :
  82.   if ( stackp == RE_run_stack_empty )
  83.   { if ( cb_ss )  *lenp = cb_e - cb_ss ;
  84.     return cb_ss ;
  85.   }
  86.   ss = stackp->ss ;
  87.   s = stackp-- -> s ;
  88.   if ( cb_ss )  /* does new state start too late ? */
  89.       if ( ss )
  90.       { if ( cb_ss < ss )  goto refill ; }
  91.       else
  92.       if ( cb_ss < s ) goto refill ;
  93.  
  94.   m = (stackp+1)->m ;
  95.   u_flag  = (stackp+1)->u ;
  96.  
  97.  
  98. reswitch  :
  99.  
  100.   switch( m->type + u_flag )
  101.   {
  102.     case M_STR + U_OFF + END_OFF :
  103.             if ( strncmp(s, m->data.str, SIZE_T(m->len)) ) goto refill ;
  104.         if ( !ss )  
  105.             if ( cb_ss && s > cb_ss ) goto refill ;
  106.         else ss = s ;
  107.             s += m->len ;  m++ ;
  108.             goto reswitch ;
  109.  
  110.     case M_STR + U_OFF + END_ON :
  111.             if ( strcmp(s, m->data.str) ) goto refill ;
  112.         if ( !ss )  
  113.             if ( cb_ss && s > cb_ss ) goto refill ;
  114.         else ss = s ;
  115.             s += m->len ;  m++ ;
  116.             goto reswitch ;
  117.  
  118.     case M_STR + U_ON + END_OFF :
  119.             if ( !(s = str_str(s, m->data.str, m->len)) ) goto refill ;
  120.             push(m, s+1,ss, U_ON) ;
  121.         if ( !ss )  
  122.             if ( cb_ss && s > cb_ss ) goto refill ;
  123.         else ss = s ;
  124.             s += m->len ; m++ ; u_flag = U_OFF ;
  125.             goto reswitch ;
  126.  
  127.     case M_STR + U_ON + END_ON :
  128.             if ( !str_end )  str_end = s + strlen(s) ;
  129.             ts = str_end - m->len ;
  130.             if (ts < s || memcmp(ts,m->data.str,SIZE_T(m->len+1))) goto refill ;
  131.         if ( !ss )  
  132.         if ( cb_ss && ts > cb_ss )  goto refill ;
  133.         else  ss = ts ;
  134.             s = str_end ; m++ ; u_flag = U_OFF ;
  135.             goto reswitch ;
  136.  
  137.     case M_CLASS + U_OFF + END_OFF :
  138.             if ( !ison(*m->data.bvp, s[0] ) )  goto refill ;
  139.         if ( !ss )
  140.         if ( cb_ss && s > cb_ss )  goto refill ;
  141.         else  ss = s ;
  142.             s++ ; m++ ;
  143.             goto reswitch ;
  144.  
  145.     case M_CLASS + U_OFF + END_ON :
  146.             if ( s[1] || !ison(*m->data.bvp,s[0]) )  goto refill ;
  147.         if ( !ss )
  148.         if ( cb_ss && s > cb_ss )  goto refill ;
  149.         else  ss = s ;
  150.             s++ ; m++ ;
  151.             goto reswitch ;
  152.  
  153.     case M_CLASS + U_ON + END_OFF :
  154.             while ( !ison(*m->data.bvp,s[0]) )
  155.                 if ( s[0] == 0 )  goto refill ;
  156.                 else  s++ ;
  157.  
  158.             s++ ;
  159.             push(m, s, ss, U_ON) ;
  160.         if ( !ss )
  161.         if ( cb_ss && s-1 > cb_ss )  goto refill ;
  162.         else  ss = s-1 ;
  163.             m++ ; u_flag = U_OFF ;
  164.             goto reswitch ;
  165.  
  166.     case M_CLASS + U_ON + END_ON :
  167.             if ( ! str_end )  str_end = s + strlen(s) ;
  168.             if ( ! ison(*m->data.bvp, str_end[-1]) ) goto refill ;
  169.         if ( !ss )
  170.         if ( cb_ss && str_end-1 > cb_ss )  goto refill ;
  171.         else  ss = str_end-1 ;
  172.             s = str_end ; m++ ; u_flag = U_OFF ;
  173.             goto reswitch ;
  174.  
  175.     case M_ANY + U_OFF + END_OFF :
  176.             if ( s[0] == 0 )  goto refill ;
  177.         if ( !ss )
  178.         if ( cb_ss && s > cb_ss )  goto refill ;
  179.         else ss = s ;
  180.             s++ ; m++ ;
  181.             goto  reswitch ;
  182.  
  183.     case M_ANY + U_OFF + END_ON :
  184.             if ( s[0] == 0 || s[1] != 0 )  goto refill ;
  185.         if ( !ss )
  186.         if ( cb_ss && s > cb_ss )  goto refill ;
  187.         else ss = s ;
  188.             s++ ; m++ ;
  189.             goto reswitch ;
  190.  
  191.     case M_ANY + U_ON + END_OFF :
  192.             if ( s[0] == 0 )  goto refill ;
  193.             s++ ; 
  194.             push(m, s, ss, U_ON) ;
  195.         if ( !ss )
  196.         if ( cb_ss && s-1 > cb_ss )  goto refill ;
  197.         else  ss = s-1 ;
  198.             m++ ; u_flag = U_OFF ;
  199.             goto  reswitch ;
  200.  
  201.     case M_ANY + U_ON + END_ON :
  202.             if ( s[0] == 0 )  goto refill ;
  203.             if ( ! str_end )  str_end = s + strlen(s) ;
  204.         if ( !ss )
  205.         if ( cb_ss && str_end-1 > cb_ss )  goto refill ;
  206.         else  ss = str_end - 1 ;
  207.             s = str_end ; m++ ; u_flag = U_OFF ;
  208.             goto reswitch ;
  209.  
  210.     case  M_START + U_OFF + END_OFF :
  211.     case  M_START + U_ON  + END_OFF :
  212.             if ( s != str )  goto  refill ;
  213.         ss = s ;
  214.             m++ ;  u_flag = U_OFF ;
  215.             goto  reswitch ;
  216.  
  217.     case  M_START + U_OFF + END_ON :
  218.     case  M_START + U_ON  + END_ON :
  219.             if ( s != str || s[0] != 0 )  goto  refill ;
  220.         ss = s ;
  221.             m++ ; u_flag = U_OFF ;
  222.             goto  reswitch ;
  223.  
  224.     case  M_END + U_OFF  :
  225.             if ( s[0]  != 0 )  goto  refill ;
  226.         if ( !ss ) 
  227.         if ( cb_ss && s > cb_ss )  goto refill ;
  228.         else  ss = s ;
  229.             m++ ; goto reswitch ;
  230.  
  231.     case  M_END + U_ON :
  232.         s = str_end ? str_end : (str_end =  s + strlen(s)) ;
  233.         if ( !ss ) 
  234.         if ( cb_ss && s > cb_ss )  goto refill ;
  235.         else  ss = s ;
  236.             m++ ; u_flag = U_OFF ;
  237.             goto reswitch ;
  238.  
  239.     CASE_UANY(M_U) :
  240.         if ( !ss ) 
  241.         if ( cb_ss && s > cb_ss )  goto refill ;
  242.         else  ss = s ;
  243.             u_flag = U_ON ; m++ ;
  244.             goto reswitch ;
  245.  
  246.     CASE_UANY(M_1J) :
  247.             m += m->data.jump ;
  248.             goto reswitch ;
  249.  
  250.     CASE_UANY(M_2JA) : /* take the non jump branch */
  251.             push(m+m->data.jump, s, ss, u_flag) ;
  252.             m++ ;
  253.             goto reswitch ;
  254.  
  255.     CASE_UANY(M_2JB) : /* take the jump branch */
  256.             push(m+1, s, ss, u_flag) ;
  257.             m += m->data.jump ;
  258.             goto reswitch ;
  259.  
  260.     case M_ACCEPT + U_OFF :
  261.         if ( !ss )  ss = s ;
  262.         if ( !cb_ss || ss < cb_ss || ss == cb_ss && s > cb_e )
  263.         { /* we have a new current best */
  264.           cb_ss = ss ; cb_e = s ;
  265.         }
  266.         goto  refill ;
  267.  
  268.     case  M_ACCEPT + U_ON :
  269.         if ( !ss )  ss = s ;
  270.         else
  271.         s = str_end ? str_end : (str_end = s + strlen(s)) ;
  272.  
  273.         if ( !cb_ss || ss < cb_ss || ss == cb_ss && s > cb_e )
  274.         { /* we have a new current best */
  275.           cb_ss = ss ; cb_e = s ;
  276.         }
  277.         goto  refill ;
  278.  
  279.     default :
  280.             RE_panic("unexpected case in REmatch") ;
  281.   }
  282. }
  283.  
  284.